package subject_set.offer100;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author haomin
 * @date 2022/10/21 18:04
 **/
public class Offer49 {
    class Solution {
        public int nthUglyNumber(int n) {
            int[] data = new int[n];
            int ret, ind2 = 0, ind3 = 0, ind5 = 0;
            data[0] = 1;
            for(int i = 1; i < n; ++i){
                ret = Math.min(data[ind2] * 2, Math.min(data[ind3] * 3, data[ind5] * 5));
                if(ret % 2 == 0) ind2++;
                if(ret % 3 == 0) ind3++;
                if(ret % 5 == 0) ind5++;
                data[i] = ret;
            }
            return data[n-1];
        }
    }
    class Solution2 {
        public int nthUglyNumber(int n) {
            Queue<Long> q = new PriorityQueue<>();
            List<Long> list = new LinkedList<>();
            long cur = 1, count = 0;
            q.add(cur);
            while(!q.isEmpty()){
                cur = q.poll();
                if(!list.contains(cur)){
                    q.add(cur * 2);
                    q.add(cur * 3);
                    q.add(cur * 5);
                    list.add(cur);
                    count++;
                }
                if(count == n) break;
            }
            return (int)cur;
        }
    }
}